#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2022/04/14
# @Author   :Changshu
# @File     :Exercise22.py
# 22. 括号生成
# 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

def generateParenthesis(n: int) -> list:
	res = []

	def backtracking(n, left, right, s):
		if right > left:
			return
		if left == right and left == n:
			res.append(s)
			return
		if left < n:
			backtracking(n, left + 1, right, s + '(')
		if right < n:
			backtracking(n, left, right + 1, s + ')')

	backtracking(n, 0, 0, '')
	return res

if __name__ == '__main__':
	# r=generateParenthesis(4)
	# print(r)
	# print(len(r))

	a=[[0 for _ in range(5)] for _ in range(4)]
	print(a)